GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Lagrange-Dualität</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Lagrange-Dualität</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Die Lagrange-Dualität ist eine wichtige <a href="Dualit%C3%A4t_(Mathematik)" title="Dualität (Mathematik)">Dualität</a> in der <a href="Optimierung_(Mathematik)" class="mw-redirect" title="Optimierung (Mathematik)">mathematischen Optimierung</a>, die sowohl <a href="Optimalit%C3%A4tskriterium" title="Optimalitätskriterium">Optimalitätskriterien</a> mittels der <a href="Karush-Kuhn-Tucker-Bedingungen" title="Karush-Kuhn-Tucker-Bedingungen">Karush-Kuhn-Tucker-Bedingungen</a> oder der <a href="Lagrange-Multiplikator" title="Lagrange-Multiplikator">Lagrange-Multiplikatoren</a> liefert als auch äquivalente Umformulierungen von <a href="Optimierungsproblem" title="Optimierungsproblem">Optimierungsproblemen</a> möglich macht.

Ziel ist es das ursprüngliche (primale) Problem in ein duales Problem zu überführen.

<div class="mw-heading mw-heading2"><h2 id="Lagrange-Funktion,_duales_Problem">Lagrange-Funktion, duales Problem</h2></div>

Gegeben sei folgendes Optimierungsproblem:

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\leq 0&i=1,\dotsc ,p\\&h_{j}(x)=0&j=1,\dotsc ,q\\&x\in X&\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e3ce8031927a324f1939652b1ffdf741a99617c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:56.49ex; height:12.343ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\leq 0&i=1,\dotsc ,p\\&h_{j}(x)=0&j=1,\dotsc ,q\\&x\in X&\end{aligned}}}" loading="lazy"></dd></dl>

Dabei kann die abstrakte Restriktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3e580967f68f36743e894aa7944f032dda6ea01d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}" loading="lazy"> beispielsweise Forderungen wie <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {Z} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {Z} ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7dad741971156e7e981a7e09df8642d457d6602b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.939ex; height:2.343ex;" alt="{\displaystyle x\in \mathbb {Z} ^{n}}" loading="lazy"> (Ganzzahligkeit) oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in {\mathcal {K}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in {\mathcal {K}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e189118f49b39ed53e3b650c415b958933564fe2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.941ex; height:2.176ex;" alt="{\displaystyle x\in {\mathcal {K}}}" loading="lazy"> für einen <a href="Kegel_(Lineare_Algebra)" title="Kegel (Lineare Algebra)">Kegel</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {K}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {K}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3a70fc5d5ef4fa8ce694447bef39c1aa167a68b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.771ex; height:2.176ex;" alt="{\displaystyle {\mathcal {K}}}" loading="lazy"> aufnehmen. Die auftretenden Funktionen müssen weder <a href="Konvexe_Funktion" class="mw-redirect" title="Konvexe Funktion">konvex</a> noch <a href="Differenzierbare_Funktion" class="mw-redirect" title="Differenzierbare Funktion">differenzierbar</a> sein.

Die Funktion

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,\lambda ,\mu ):=f(x)+\sum _{i=1}^{p}\lambda _{i}g_{i}(x)+\sum _{j=1}^{q}\mu _{j}h_{j}(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ae5658f900c70cf403ff5c4c44761e8a684aa08c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:45.776ex; height:7.343ex;" alt="{\displaystyle L(x,\lambda ,\mu ):=f(x)+\sum _{i=1}^{p}\lambda _{i}g_{i}(x)+\sum _{j=1}^{q}\mu _{j}h_{j}(x)}" loading="lazy"></dd></dl>

heißt dann die zu dem obigen Optimierungsproblem gehörende Lagrange-Funktion. Gelegentlich werden die Funktionen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i},h_{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i},h_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ab0bf6892c2b92c0993b60ddb13c132a3343fc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.191ex; height:2.843ex;" alt="{\displaystyle g_{i},h_{j}}" loading="lazy"> sowie die Skalare <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{i},\mu _{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i},\mu _{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4d730da1eb7fd6164e9906c39f362d840a71eba0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.5ex; height:2.843ex;" alt="{\displaystyle \lambda _{i},\mu _{j}}" loading="lazy"> zu Vektoren <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)=(g_{1}(x),\dots ,g_{p}(x))^{T},h(x)=(h_{1}(x),\dots ,h_{q}(x))^{T}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)=(g_{1}(x),\dots ,g_{p}(x))^{T},h(x)=(h_{1}(x),\dots ,h_{q}(x))^{T}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6c8d33a5e8bb2e669288357513a58e849a4d9e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:54.325ex; height:3.343ex;" alt="{\displaystyle g(x)=(g_{1}(x),\dots ,g_{p}(x))^{T},h(x)=(h_{1}(x),\dots ,h_{q}(x))^{T}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda =(\lambda _{1},\dots ,\lambda _{p})^{T},\mu =(\mu _{1},\dots ,\mu _{q})^{T}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda =(\lambda _{1},\dots ,\lambda _{p})^{T},\mu =(\mu _{1},\dots ,\mu _{q})^{T}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6b2e327ccdfe6e9cb867c44052736c6e2ceaf9f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:36.411ex; height:3.343ex;" alt="{\displaystyle \lambda =(\lambda _{1},\dots ,\lambda _{p})^{T},\mu =(\mu _{1},\dots ,\mu _{q})^{T}}" loading="lazy"> zusammengefasst. Die Lagrange-Funktion vereinfacht sich dann zu

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,\lambda ,\mu ):=f(x)+\lambda ^{T}g(x)+\mu ^{T}h(x).}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b3e1c5e146003b4c5a26621432ee7e957570a8cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:38.306ex; height:3.176ex;" alt="{\displaystyle L(x,\lambda ,\mu ):=f(x)+\lambda ^{T}g(x)+\mu ^{T}h(x).}" loading="lazy"></dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ,\mu )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba8cdbd5709dd03200b2d3a796bf19a9f8be7482.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.6ex; height:2.843ex;" alt="{\displaystyle (\lambda ,\mu )}" loading="lazy"> werden duale Variablen oder <a href="Lagrange-Multiplikator" title="Lagrange-Multiplikator">Lagrange-Multiplikatoren</a> genannt. Die Funktion

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(\lambda ,\mu )=\inf _{x\in X}L(x,\lambda ,\mu )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3fb4774c94a02daefa5ed4a94d73ad1651afdd45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:23.138ex; height:4.009ex;" alt="{\displaystyle q(\lambda ,\mu )=\inf _{x\in X}L(x,\lambda ,\mu )}" loading="lazy"></dd></dl>

heißt dann die duale Funktion zu dem obigen Optimierungsproblem. Das Optimierungsproblem

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )\\{\text{unter den Nebenbedingungen }}&\lambda \geq 0\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f7629ed6f9f17cb96316686398eac7593f11ce30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:37.399ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )\\{\text{unter den Nebenbedingungen }}&\lambda \geq 0\end{aligned}}}" loading="lazy"></dd></dl>

heißt das duale Problem des obigen Optimierungsproblems. Dabei ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda \geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda \geq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0c26004859ae51dde7800b3f3a960c73f81cd583.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.616ex; height:2.343ex;" alt="{\displaystyle \lambda \geq 0}" loading="lazy"> komponentenweise zu verstehen. Das ursprüngliche Problem wird dann auch als primales Problem bezeichnet. Im Allgemeinen muss die duale Funktion nicht reellwertig sein, sie kann durchaus auch den Wert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -\infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -\infty }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ca2608c4b5fd3bffc73585f8c67e379b4e99b6f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.132ex; height:2.176ex;" alt="{\displaystyle -\infty }" loading="lazy"> annehmen. Man definiert dann

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {dom} _{q}:=\{(\lambda ,\mu )\in \mathbb {R} ^{p}\times \mathbb {R} ^{q}\,|\,\lambda \geq 0,q(\lambda ,\mu )>-\infty \}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {dom} _{q}:=\{(\lambda ,\mu )\in \mathbb {R} ^{p}\times \mathbb {R} ^{q}\,|\,\lambda \geq 0,q(\lambda ,\mu )>-\infty \}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a415729de338bb369b61a560de04b22ecb6e7be4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:50.106ex; height:3.009ex;" alt="{\displaystyle \operatorname {dom} _{q}:=\{(\lambda ,\mu )\in \mathbb {R} ^{p}\times \mathbb {R} ^{q}\,|\,\lambda \geq 0,q(\lambda ,\mu )>-\infty \}}" loading="lazy"></dd></dl>

als den <a href="Wesentlicher_Definitionsbereich" class="mw-redirect" title="Wesentlicher Definitionsbereich">wesentlichen Definitionsbereich</a> der dualen Funktion. Die dualen Variablen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\lambda ,\mu )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ,\mu )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba8cdbd5709dd03200b2d3a796bf19a9f8be7482.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.6ex; height:2.843ex;" alt="{\displaystyle (\lambda ,\mu )}" loading="lazy"> werden dual zulässig genannt, wenn sie zulässig bezüglich des dualen Problems sind, das heißt, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda \geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda \geq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0c26004859ae51dde7800b3f3a960c73f81cd583.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.616ex; height:2.343ex;" alt="{\displaystyle \lambda \geq 0}" loading="lazy"> gilt.

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

Betrachtet man als Beispiel ein <a href="Lineare_Optimierung" title="Lineare Optimierung">lineares Optimierungsproblem</a> in Ungleichungsform:

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&Ax-b\leq 0\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f858d606c7e5969ee822c04d4aa248fd470a55ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.265ex; margin-bottom: -0.24ex; width:41.971ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&Ax-b\leq 0\end{aligned}}}" loading="lazy"></dd></dl>

Dabei ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,c\in \mathbb {R} ^{n}\,,b\in \mathbb {R} ^{m}}">

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,c\in \mathbb {R} ^{n}\,,b\in \mathbb {R} ^{m}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/176b62b34ce3ba915be71288d3b615ffd767688a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.72ex; height:2.676ex;" alt="{\displaystyle x,c\in \mathbb {R} ^{n}\,,b\in \mathbb {R} ^{m}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\in \mathbb {R} ^{m\times n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\in \mathbb {R} ^{m\times n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8025ab71ecd74b01e89f6918676203ad16cdc4a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.202ex; height:2.343ex;" alt="{\displaystyle A\in \mathbb {R} ^{m\times n}}" loading="lazy">. Der Vollständigkeit halber setzt man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=\mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X=\mathbb {R} ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/16344851ca00c2c8c6c80f658d1a180eb94abee9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.975ex; height:2.343ex;" alt="{\displaystyle X=\mathbb {R} ^{n}}" loading="lazy">, was in diesem Fall keine Einschränkung bedeutet. Die Lagrange-Funktion ist dann

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,\lambda )=c^{T}x+\lambda ^{T}(Ax-b)=(c^{T}+\lambda ^{T}A)x-\lambda ^{T}b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9b9004ec5ebf5c41a2f5b0d9911f4ad8a10e1ef0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:50.784ex; height:3.176ex;" alt="{\displaystyle L(x,\lambda )=c^{T}x+\lambda ^{T}(Ax-b)=(c^{T}+\lambda ^{T}A)x-\lambda ^{T}b}" loading="lazy">.</dd></dl>

Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c^{T}=-\lambda ^{T}A}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{T}=-\lambda ^{T}A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d874c9a6f48deda50959221dd179586a3b3b3d28.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.79ex; height:2.843ex;" alt="{\displaystyle c^{T}=-\lambda ^{T}A}" loading="lazy">, so ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(x,\lambda )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,\lambda )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f9d0599be5c2f9b29802ad4a026187797ef5442b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.111ex; height:2.843ex;" alt="{\displaystyle L(x,\lambda )}" loading="lazy"> unabhängig von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> und damit ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \inf _{x\in X}L(x,\lambda )=-\lambda ^{T}b}">

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \inf _{x\in X}L(x,\lambda )=-\lambda ^{T}b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/60a06ed57841539de2e9e5b38389679306543e2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:19.583ex; height:4.343ex;" alt="{\displaystyle \inf _{x\in X}L(x,\lambda )=-\lambda ^{T}b}" loading="lazy">. Ist aber <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c^{T}\neq -\lambda ^{T}A}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{T}\neq -\lambda ^{T}A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/63d973689f437ae1c9702abbee00b2e921a9e458.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.79ex; height:3.176ex;" alt="{\displaystyle c^{T}\neq -\lambda ^{T}A}" loading="lazy">, so ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(x,\lambda )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,\lambda )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f9d0599be5c2f9b29802ad4a026187797ef5442b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.111ex; height:2.843ex;" alt="{\displaystyle L(x,\lambda )}" loading="lazy"> in eine Richtung nach unten unbeschränkt und demnach gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \inf _{x\in X}L(x,\lambda )=-\infty }">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \inf _{x\in X}L(x,\lambda )=-\infty }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/194d9cf77e6148e0f8e4e1dcd9842f74d7a9ca7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:18.165ex; height:4.009ex;" alt="{\displaystyle \inf _{x\in X}L(x,\lambda )=-\infty }" loading="lazy">. Somit lautet die duale Funktion:

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

<mtext> falls </mtext>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext> sonst </mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(\lambda )={\begin{cases}-\lambda ^{T}b&{\text{ falls }}c^{T}+\lambda ^{T}A=0\\-\infty &{\text{ sonst }}\end{cases}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6fbd997cbb246fd210e98a8cf7b7c0edbda6f244.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:36.93ex; height:6.176ex;" alt="{\displaystyle q(\lambda )={\begin{cases}-\lambda ^{T}b&{\text{ falls }}c^{T}+\lambda ^{T}A=0\\-\infty &{\text{ sonst }}\end{cases}}}" loading="lazy"></dd></dl>

Schreibt man nun die Fallunterscheidung aus der dualen Funktion als <a href="Nebenbedingung" title="Nebenbedingung">Nebenbedingung</a> in das duale Problem, so erhält man:

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&-\lambda ^{T}b\\{\text{unter den Nebenbedingungen }}&A^{T}\lambda +c=0\\&\lambda \geq 0\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1704dd0398a2eb4a07dcde84ab6c1ccdb715b3cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:43.325ex; height:9.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&-\lambda ^{T}b\\{\text{unter den Nebenbedingungen }}&A^{T}\lambda +c=0\\&\lambda \geq 0\end{aligned}}}" loading="lazy"></dd></dl>

Dies ist genau ein lineares Optimierungsproblem in Standardform.

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften_des_dualen_Problems">Eigenschaften des dualen Problems</h2></div>

<ul><li>Die Definitionsmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {dom} _{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {dom} _{q}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9d1c3ef99d2e1e1836eab4f623d601f5f85ada79.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.379ex; height:2.843ex;" alt="{\displaystyle \operatorname {dom} _{q}}" loading="lazy"> der dualen Funktion ist <a href="Konvexe_Menge" title="Konvexe Menge">konvex</a>.</li>

<li>Die duale Funktion ist <a href="Konkave_Funktion" class="mw-redirect" title="Konkave Funktion">konkav</a>. Für fixiertes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {x}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tilde {x}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f5c5435030c952a58a756e691ea64f60c1bd240.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:2.176ex;" alt="{\displaystyle {\tilde {x}}}" loading="lazy"> ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L({\tilde {x}},\lambda ,\mu )}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L({\tilde {x}},\lambda ,\mu )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c2da86cfe64b76213e57aa1047a23ccb6323139c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.547ex; height:2.843ex;" alt="{\displaystyle L({\tilde {x}},\lambda ,\mu )}" loading="lazy"> eine <a href="Affine_Abbildung" title="Affine Abbildung">affine Funktion</a> und damit ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q(\lambda ,\mu )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(\lambda ,\mu )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a3ee5f367081586b9a3904ce85530642ef9aac17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.67ex; height:2.843ex;" alt="{\displaystyle q(\lambda ,\mu )}" loading="lazy"> als punktweises Infimum von affinen Funktionen konkav. Somit ist das duale Problem immer ein <a href="Konvexe_Optimierung" title="Konvexe Optimierung">konvexes Optimierungsproblem</a>, unabhängig von der Struktur des primalen Problems.</li>

<li>Daher sind konvexe Optimierungsprobleme eine Klasse von Problemen, deren duales Problem wieder in derselben Problemklasse liegt. Weitere solche Klassen sind die lineare Optimierungsprobleme (siehe Beispiel), die <a href="Konisches_Programm" title="Konisches Programm">konischen Programme</a> sowie die <a href="Semidefinite_Programmierung" title="Semidefinite Programmierung">semidefiniten Programme</a> und die <a href="SOCP" title="SOCP">SOCPs</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Schwache_Dualität">Schwache Dualität</h2></div>

Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{P}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{P}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/203847b56e637a9df11d99c36e336e87632dd566.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.23ex; height:2.509ex;" alt="{\displaystyle R_{P}}" loading="lazy"> die Restriktionsmenge des primalen Problems und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {dom} _{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {dom} _{q}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9d1c3ef99d2e1e1836eab4f623d601f5f85ada79.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.379ex; height:2.843ex;" alt="{\displaystyle \operatorname {dom} _{q}}" loading="lazy"> die <a href="Definitionsmenge" title="Definitionsmenge">Definitionsmenge</a> des dualen Problems.

Dann gilt für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in R_{P}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in R_{P}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/764cfc22066bdbb65434fd11124599402c11aeca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.401ex; height:2.509ex;" alt="{\displaystyle x\in R_{P}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\lambda ,\mu )\in \operatorname {dom} _{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ,\mu )\in \operatorname {dom} _{q}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2d4d3077027932a943e96785117372b81269d758.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.82ex; height:3.009ex;" alt="{\displaystyle (\lambda ,\mu )\in \operatorname {dom} _{q}}" loading="lazy">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(\lambda ,\mu )\leq f(x).}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bef62705317d82bf569b69861edd6e668cb7782e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.833ex; height:2.843ex;" alt="{\displaystyle q(\lambda ,\mu )\leq f(x).}" loading="lazy"></dd></dl>

Der Wert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)-q(\lambda ,\mu )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)-q(\lambda ,\mu )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6ed0f0185320305723c459fceb2cec81ac09088a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.928ex; height:2.843ex;" alt="{\displaystyle f(x)-q(\lambda ,\mu )}" loading="lazy"> heißt dann die Dualitätslücke (des zulässigen Punktes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,\lambda ,\mu )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,\lambda ,\mu )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8092181e0af3a9be77f8c7d07c694ca61dfa06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.964ex; height:2.843ex;" alt="{\displaystyle (x,\lambda ,\mu )}" loading="lazy">). Die duale Funktion ist also immer eine untere Schranke für die Zielfunktion des primalen Problems. Somit lässt sich auch das duale Problem motivieren: Es stellt die Frage nach der größten unteren Schranke für das primale Problem, die noch zulässig ist.

Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=f(R_{P})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=f(R_{P})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d1a88b01cac9d75748934fe407e09ce36b6078f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.162ex; height:2.843ex;" alt="{\displaystyle P=f(R_{P})}" loading="lazy"> die Wertemenge des primalen Problems und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D=q(\operatorname {dom} _{q})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D=q(\operatorname {dom} _{q})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9f431fda2d9ad6a434f7e183e96b39453d68faf7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.281ex; height:3.009ex;" alt="{\displaystyle D=q(\operatorname {dom} _{q})}" loading="lazy"> die des dualen Problems, so gilt

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sup(D)\leq \inf(P)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1aa398304af761b5f8fb0f0ed9343542992e82a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.539ex; height:2.843ex;" alt="{\displaystyle \sup(D)\leq \inf(P)}" loading="lazy">.</dd></dl>

Der Wert der dualen Optimallösung ist also stets kleiner als der Wert der primalen Optimallösung. Diese Aussage wird auch schwache Dualität genannt. Der Wert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \inf(P)-\sup(D)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \inf(P)-\sup(D)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/61f432e0b24ec64aa051f8f148450596b328c500.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.281ex; height:2.843ex;" alt="{\displaystyle \inf(P)-\sup(D)}" loading="lazy"> heißt dann die optimale Dualitätslücke.

Diese Aussagen folgen direkt aus

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</munder>

<mover>

</mover>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<mover>

</mover>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}q(\lambda ,\mu )&=\inf _{x\in X}L(x,\lambda ,\mu )\leq L({\tilde {x}},\lambda ,\mu )\\&=f({\tilde {x}})+\sum _{i=1}^{p}\lambda _{i}g_{i}({\tilde {x}})+\sum _{j=1}^{q}\mu _{j}h_{j}({\tilde {x}})\leq f({\tilde {x}})\quad {\text{für alle }}(\lambda ,\mu )\in \operatorname {dom} _{q}{\text{ und }}{\tilde {x}}\in R_{P}.\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b36b579bc8e3e1d62b1a3294ef59a1185c4bffe3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.028ex; margin-bottom: -0.31ex; width:87.826ex; height:11.843ex;" alt="{\displaystyle {\begin{aligned}q(\lambda ,\mu )&=\inf _{x\in X}L(x,\lambda ,\mu )\leq L({\tilde {x}},\lambda ,\mu )\\&=f({\tilde {x}})+\sum _{i=1}^{p}\lambda _{i}g_{i}({\tilde {x}})+\sum _{j=1}^{q}\mu _{j}h_{j}({\tilde {x}})\leq f({\tilde {x}})\quad {\text{für alle }}(\lambda ,\mu )\in \operatorname {dom} _{q}{\text{ und }}{\tilde {x}}\in R_{P}.\end{aligned}}}" loading="lazy"></dd></dl>

Dabei folgt die letzte Ungleichung, da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}({\tilde {x}})\leq 0}">

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}({\tilde {x}})\leq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b632453c9f2726606e86cb3ce9222b93303d4f0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.309ex; height:2.843ex;" alt="{\displaystyle g_{i}({\tilde {x}})\leq 0}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{j}({\tilde {x}})=0}">

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{j}({\tilde {x}})=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cba76fc3fa8e50c86edf7327e8d9bedfa7ab0280.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.649ex; height:3.009ex;" alt="{\displaystyle h_{j}({\tilde {x}})=0}" loading="lazy"> (Zulässigkeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {x}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tilde {x}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f5c5435030c952a58a756e691ea64f60c1bd240.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:2.176ex;" alt="{\displaystyle {\tilde {x}}}" loading="lazy">) und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{i}\geq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}\geq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f9eb29859cc5545bc3c19b0fc9d14e23fce79367.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.416ex; height:2.509ex;" alt="{\displaystyle \lambda _{i}\geq 0}" loading="lazy"> (Zulässigkeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b43d0ea3c9c025af1be9128e62a18fa74bedda2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }" loading="lazy">) und damit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{i}g_{i}({\tilde {x}})\leq 0}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}g_{i}({\tilde {x}})\leq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fde0ee933c7e23911a5cfc7846e61d843acc8f9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.464ex; height:2.843ex;" alt="{\displaystyle \lambda _{i}g_{i}({\tilde {x}})\leq 0}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{i}h_{i}({\tilde {x}})=0}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{i}h_{i}({\tilde {x}})=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5c343acd91f9ae7ef6e7412e2ef6c2c710682e40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.74ex; height:2.843ex;" alt="{\displaystyle \mu _{i}h_{i}({\tilde {x}})=0}" loading="lazy">. Da die Ungleichung für beliebige <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\lambda ,\mu )\in \operatorname {dom_{q}} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ,\mu )\in \operatorname {dom_{q}} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/197243e1f3ff95fb9f22f5dd86a8a983addc674e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.943ex; height:3.009ex;" alt="{\displaystyle (\lambda ,\mu )\in \operatorname {dom_{q}} }" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {x}}\in R_{P}}">

<mover>

</mover>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tilde {x}}\in R_{P}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ab5b9ebb29b7eef10f7c571fdcad717613bd5531.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.401ex; height:2.509ex;" alt="{\displaystyle {\tilde {x}}\in R_{P}}" loading="lazy"> gilt, folgen die beiden obigen Aussagen.

<div class="mw-heading mw-heading2"><h2 id="Starke_Dualität">Starke Dualität</h2></div>

Unter gewissen Umständen stimmen der Optimalwert des primalen Problems und der des dualen Problems überein, die optimale Dualitätslücke ist also Null. Es gilt dann

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sup(D)=\inf(P)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bc0e18fd8cfd364364857a0654eaaf3156c41f78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.539ex; height:2.843ex;" alt="{\displaystyle \sup(D)=\inf(P)}" loading="lazy">.</dd></dl>

Dieser Fall wird dann starke Dualität genannt. Gilt starke Dualität und ist der Optimalwert endlich und wird in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"> bzw. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\lambda ^{*},\mu ^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f67506f38347e50c76fbd7282a5d3bbe89a5c612.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.709ex; height:2.843ex;" alt="{\displaystyle (\lambda ^{*},\mu ^{*})}" loading="lazy"> angenommen, so gilt:

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sup(D)=\inf(P)=f(x^{*})=q(\lambda ^{*},\mu ^{*})=L(x^{*},\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1a92509f479c72308dfd836eeb8da803e5d80c23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:52.794ex; height:2.843ex;" alt="{\displaystyle \sup(D)=\inf(P)=f(x^{*})=q(\lambda ^{*},\mu ^{*})=L(x^{*},\lambda ^{*},\mu ^{*})}" loading="lazy"></dd></dl>

Im Allgemeinen gilt starke Dualität nicht, sondern es müssen noch weitere Regularitätsvoraussetzungen (im Englischen constraint qualifications) an das Problem erfüllt sein. Eine der wichtigsten Voraussetzungen für <a href="Konvexe_Optimierung" title="Konvexe Optimierung">konvexe Optimierungsprobleme</a> und <a href="Fast-konvexe_Funktion" title="Fast-konvexe Funktion">fast-konvexe Funktionen</a>, unter der starke Dualität gilt, ist zum Beispiel die <a href="Slater-Bedingung" title="Slater-Bedingung">Slater-Bedingung</a>.

<div class="mw-heading mw-heading2"><h2 id="Komplementärer_Schlupf">Komplementärer Schlupf</h2></div>

<div class="hauptartikel" role="navigation">→ Hauptartikel: <a href="Komplement%C3%A4rer_Schlupf" class="mw-redirect" title="Komplementärer Schlupf">Komplementärer Schlupf</a></div>

Gilt die starke Dualität, sind <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\lambda ^{*},\mu ^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f67506f38347e50c76fbd7282a5d3bbe89a5c612.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.709ex; height:2.843ex;" alt="{\displaystyle (\lambda ^{*},\mu ^{*})}" loading="lazy"> primal bzw. dual optimal und ist der Optimalwert endlich, so gilt die complementary slackness, auch komplementärer Schlupf genannt:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}g_{i}(x^{*})=0{\text{ für alle }}i=1,\dotsc ,p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5590d4fdcc568ef5017bfe3921b9bdcc5bdd2c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:32.199ex; height:3.343ex;" alt="{\displaystyle \lambda _{i}g_{i}(x^{*})=0{\text{ für alle }}i=1,\dotsc ,p}" loading="lazy"></dd></dl>

Ist der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-te Lagrange-Multiplikator (die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-te Ungleichungsrestriktion) ungleich null, so muss die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-te Ungleichungsrestriktion (der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-te Lagrange-Multiplikator) gleich null sein:

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}\lambda _{i}>0\implies g_{i}(x^{*})=0\\g_{i}(x^{*})<0\implies \lambda _{i}=0\end{aligned}}}">

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\lambda _{i}>0\implies g_{i}(x^{*})=0\\g_{i}(x^{*})<0\implies \lambda _{i}=0\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/836df28d9d6d1e566a00da883807f6a043dd670c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:23.916ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}\lambda _{i}>0\implies g_{i}(x^{*})=0\\g_{i}(x^{*})<0\implies \lambda _{i}=0\end{aligned}}}" loading="lazy"></dd></dl>

Dies folgt aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{i}\geq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}\geq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f9eb29859cc5545bc3c19b0fc9d14e23fce79367.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.416ex; height:2.509ex;" alt="{\displaystyle \lambda _{i}\geq 0}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}(x^{*})\leq 0}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}(x^{*})\leq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/981c0d17f5bb0b07391fd36ca2c9b8bfee30e3cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.363ex; height:2.843ex;" alt="{\displaystyle g_{i}(x^{*})\leq 0}" loading="lazy">. Es muss also stets mindestens einer der beiden Faktoren null sein.

<div class="mw-heading mw-heading2"><h2 id="Sattelpunkte">Sattelpunkte</h2></div>

Ein Punkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x^{*},\lambda ^{*},\mu ^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x^{*},\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f69a88d3bd2af0e22f2b31e842b63be81beb6dd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.126ex; height:2.843ex;" alt="{\displaystyle (x^{*},\lambda ^{*},\mu ^{*})}" loading="lazy"> heißt ein <a href="Sattelpunkt" title="Sattelpunkt">Sattelpunkt</a> der Lagrange-Funktion, wenn für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,\lambda ,\mu )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,\lambda ,\mu )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8092181e0af3a9be77f8c7d07c694ca61dfa06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.964ex; height:2.843ex;" alt="{\displaystyle (x,\lambda ,\mu )}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda \geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda \geq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0c26004859ae51dde7800b3f3a960c73f81cd583.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.616ex; height:2.343ex;" alt="{\displaystyle \lambda \geq 0}" loading="lazy">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x^{*},\lambda ,\mu )\leq L(x^{*},\lambda ^{*},\mu ^{*})\leq L(x,\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/221a8844dfe319e6aac0e574b8a483549591a949.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:41.162ex; height:2.843ex;" alt="{\displaystyle L(x^{*},\lambda ,\mu )\leq L(x^{*},\lambda ^{*},\mu ^{*})\leq L(x,\lambda ^{*},\mu ^{*})}" loading="lazy"></dd></dl>

gilt. Äquivalent dazu ist

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \inf _{x\in X}\sup _{(\lambda ,\mu )\in dom_{q}}L(x,\lambda ,\mu )=L(x^{*},\lambda ^{*},\mu ^{*})=\sup _{(\lambda ,\mu )\in dom_{q}}\inf _{x\in X}L(x,\lambda ,\mu ).}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b1374dccc5b2b24c477848c088f02f6b704d19e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:64.389ex; height:5.009ex;" alt="{\displaystyle \inf _{x\in X}\sup _{(\lambda ,\mu )\in dom_{q}}L(x,\lambda ,\mu )=L(x^{*},\lambda ^{*},\mu ^{*})=\sup _{(\lambda ,\mu )\in dom_{q}}\inf _{x\in X}L(x,\lambda ,\mu ).}" loading="lazy"></dd></dl>

Dies bedeutet, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\lambda ^{*},\mu ^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f67506f38347e50c76fbd7282a5d3bbe89a5c612.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.709ex; height:2.843ex;" alt="{\displaystyle (\lambda ^{*},\mu ^{*})}" loading="lazy"> ein Maximum der Lagrange-Funktion für fixiertes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"> ein Minimum der Lagrange-Funktion für fixiertes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\lambda ^{*},\mu ^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f67506f38347e50c76fbd7282a5d3bbe89a5c612.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.709ex; height:2.843ex;" alt="{\displaystyle (\lambda ^{*},\mu ^{*})}" loading="lazy"> ist.

Es lässt sich zeigen, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x^{*},\lambda ^{*},\mu ^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x^{*},\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f69a88d3bd2af0e22f2b31e842b63be81beb6dd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.126ex; height:2.843ex;" alt="{\displaystyle (x^{*},\lambda ^{*},\mu ^{*})}" loading="lazy"> genau dann ein Sattelpunkt der Lagrange-Funktion ist, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"> primal optimal ist, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\lambda ^{*},\mu ^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f67506f38347e50c76fbd7282a5d3bbe89a5c612.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.709ex; height:2.843ex;" alt="{\displaystyle (\lambda ^{*},\mu ^{*})}" loading="lazy"> dual optimal ist und starke Dualität gilt.

Sattelpunkte spielen eine wichtige Rolle bei der Bestimmung von Optimalpunkten und schlagen eine Verbindung zu den <a href="Karush-Kuhn-Tucker-Bedingungen" title="Karush-Kuhn-Tucker-Bedingungen">Karush-Kuhn-Tucker-Bedingungen</a> und den <a href="Lagrange-Multiplikator" title="Lagrange-Multiplikator">Lagrange-Multiplikatoren</a>. Sind zum Beispiel alle beteiligten Funktionen stetig differenzierbar, so lässt sich aus dem Sattelpunktkriterium ableiten, dass an einem Optimalpunkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nabla _{x}L(x^{*},\lambda ^{*},\mu ^{*})=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0f7b4ac34242c65388128c13c7644abcf6ca3577.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.079ex; height:2.843ex;" alt="{\displaystyle \nabla _{x}L(x^{*},\lambda ^{*},\mu ^{*})=0}" loading="lazy"></dd></dl>

gelten muss, da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"> nach der Sattelpunktcharakterisierung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(x,\lambda ^{*},\mu ^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,\lambda ^{*},\mu ^{*})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1d730d341a3cb633f72c0df6b729742a516cb2e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.655ex; height:2.843ex;" alt="{\displaystyle L(x,\lambda ^{*},\mu ^{*})}" loading="lazy"> minimiert. Diese Forderung findet sich zum Beispiel in den <a href="Karush-Kuhn-Tucker-Bedingungen" title="Karush-Kuhn-Tucker-Bedingungen">Karush-Kuhn-Tucker-Bedingungen</a> zur Bestimmung eines Optimalpunktes und als notwendiges <a href="Optimalit%C3%A4tskriterium" title="Optimalitätskriterium">Optimalitätskriterium</a> wieder.

<div class="mw-heading mw-heading2"><h2 id="Allgemeinere_Formulierungen">Allgemeinere Formulierungen</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Formulierung_für_Hilberträume">Formulierung für Hilberträume</h3></div>

Betrachtet man ein Optimierungsproblem mit <a href="Verallgemeinerte_Ungleichung" title="Verallgemeinerte Ungleichung">verallgemeinerten Ungleichungen</a> zwischen reellen <a href="Hilbertraum" title="Hilbertraum">Hilberträumen</a> (also reellen <a href="Vollst%C3%A4ndiger_Raum" title="Vollständiger Raum">vollständigen Vektorräumen</a>, die mit einem <a href="Skalarprodukt" title="Skalarprodukt">Skalarprodukt</a> versehen sind), so ist dies meist von folgender Form:

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\preccurlyeq _{K_{i}}0&i=1,\dotsc ,p\\&h_{j}(x)=0&j=1,\dotsc ,q\\&x\in X&\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a98a6ab4ffde15712b22cf9670d2834926265730.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:58.402ex; height:12.509ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\preccurlyeq _{K_{i}}0&i=1,\dotsc ,p\\&h_{j}(x)=0&j=1,\dotsc ,q\\&x\in X&\end{aligned}}}" loading="lazy"></dd></dl>

Hierbei sind <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:V_{0}\mapsto \mathbb {R} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:V_{0}\mapsto \mathbb {R} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b99e65fa8c5f4fc91c75c4d0d922d09543eadad2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.917ex; height:2.509ex;" alt="{\displaystyle f:V_{0}\mapsto \mathbb {R} }" loading="lazy"> die Zielfunktion, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}:V_{0}\mapsto V_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}:V_{0}\mapsto V_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a0cb1c47148264c347124bb685d2fc414065a848.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.024ex; height:2.509ex;" alt="{\displaystyle g_{i}:V_{0}\mapsto V_{i}}" loading="lazy"> die Ungleichungsrestriktionsfunktionen und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{j}:V_{0}\mapsto V_{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{j}:V_{0}\mapsto V_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c7f8b43dac32dd25b97476cc35868b0e7d987a87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.474ex; height:2.843ex;" alt="{\displaystyle h_{j}:V_{0}\mapsto V_{j}}" loading="lazy"> die Gleichheitsrestriktionsfunktionen. Die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f300b83673e961a9d48f3862216b167f94e5668c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.155ex; height:2.509ex;" alt="{\displaystyle V_{i}}" loading="lazy"> seien mit dem <a href="Echter_Kegel" class="mw-redirect" title="Echter Kegel">echten Kegel</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/719736a1feb0bd7e73bb1425641a61229f55bb6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.773ex; height:2.509ex;" alt="{\displaystyle K_{i}}" loading="lazy"> ausgestattet, der die verallgemeinerte Ungleichung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \preccurlyeq _{K_{i}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \preccurlyeq _{K_{i}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0e1b7e22ce36d0689cd0ebdd68faadf8088e6152.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.06ex; height:2.676ex;" alt="{\displaystyle \preccurlyeq _{K_{i}}}" loading="lazy"> induziert.

Das zum Vektorraum <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{s}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{s}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/57d5d0bb9d326d015df44456d7c0648f80c0f1f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.359ex; height:2.509ex;" alt="{\displaystyle V_{s}}" loading="lazy"> gehörende Skalarprodukt sei mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle \cdot ;\cdot \rangle _{s}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle \cdot ;\cdot \rangle _{s}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/105ebd3101ea0a569420b31c787f3bb2bca0e878.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.14ex; height:2.843ex;" alt="{\displaystyle \langle \cdot ;\cdot \rangle _{s}}" loading="lazy"> bezeichnet. Man setzt dann <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda :=(\lambda _{1},\dots ,\lambda _{p})^{T},\mu :=(\mu _{1},\dots ,\mu _{q})^{T}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda :=(\lambda _{1},\dots ,\lambda _{p})^{T},\mu :=(\mu _{1},\dots ,\mu _{q})^{T}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9dac91395f44ed38a5c4c37db44df2c33a079ad7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:37.705ex; height:3.343ex;" alt="{\displaystyle \lambda :=(\lambda _{1},\dots ,\lambda _{p})^{T},\mu :=(\mu _{1},\dots ,\mu _{q})^{T}}" loading="lazy">. Dabei gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{i}\in V_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}\in V_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ad05dc8a3acb3d1c680b4b5c294bd456019bca06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.15ex; height:2.509ex;" alt="{\displaystyle \lambda _{i}\in V_{i}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{j}\in V_{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{j}\in V_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b2bd4a6f127026249afd61dcd0db33b853e2fcce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.417ex; height:2.843ex;" alt="{\displaystyle \mu _{j}\in V_{j}}" loading="lazy">.

Dann ist die Lagrange-Funktion von der Form

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,\lambda ,\mu ):=f(x)+\sum _{i=1}^{p}\langle \lambda _{i};g_{i}(x)\rangle _{i}+\sum _{j=1}^{q}\langle \mu _{j};h_{j}(x)\rangle _{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/61d44787035fd8a6fdff55c19b3cb5e229499820.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:52.398ex; height:7.343ex;" alt="{\displaystyle L(x,\lambda ,\mu ):=f(x)+\sum _{i=1}^{p}\langle \lambda _{i};g_{i}(x)\rangle _{i}+\sum _{j=1}^{q}\langle \mu _{j};h_{j}(x)\rangle _{j}}" loading="lazy"></dd></dl>

und die duale Funktion lautet

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(\lambda ,\mu )=\inf _{x\in X}L(x,\lambda ,\mu ).}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a763b9a0032dbf42f11acfb0fdddb078f36c805d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:23.785ex; height:4.009ex;" alt="{\displaystyle q(\lambda ,\mu )=\inf _{x\in X}L(x,\lambda ,\mu ).}" loading="lazy"></dd></dl>

Das duale Problem lautet dann:

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda _{i}\succcurlyeq _{K^{D}}0&i=1,\dotsc ,p\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c031c4308228ac916911ad1a643ab9fcd3793e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.278ex; margin-bottom: -0.226ex; width:56.183ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda _{i}\succcurlyeq _{K^{D}}0&i=1,\dotsc ,p\end{aligned}}}" loading="lazy">,</dd></dl>

Dabei ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K^{D}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K^{D}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bf20270303d5d7f4eaae55e930239a52b0bc4c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.687ex; height:2.676ex;" alt="{\displaystyle K^{D}}" loading="lazy"> der <a href="Dualer_Kegel" title="Dualer Kegel">duale Kegel</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy">.

Alternative Formulierungen fassen alle Ungleichungsrestriktionen und Gleichheitsrestriktionen zusammen:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)=(g_{1}(x),\dots ,g_{p}(x))^{T}\,,\,h(x)=(h_{1}(x),\dots ,h_{j}(x))^{T},K:=K_{1}\times \dots \times K_{p}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1da0f3b24fa760ca2a3ece4ae7089f706044797a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:76.33ex; height:3.343ex;" alt="{\displaystyle g(x)=(g_{1}(x),\dots ,g_{p}(x))^{T}\,,\,h(x)=(h_{1}(x),\dots ,h_{j}(x))^{T},K:=K_{1}\times \dots \times K_{p}}" loading="lazy"></dd></dl>

Dies führt zu einer kompakteren Schreibweise, die ohne Summenzeichen und Indizes auskommt und daher für theoretische Betrachtungen bevorzugt wird. Alternativ wird auch die Forderung nach einem echten Kegel abgeschwächt, stattdessen definiert man die Ungleichung nur durch einen <a href="Ordnungskegel" title="Ordnungskegel">Ordnungskegel</a>, der zumindest konvex sein muss. Manchmal wir auch komplett auf Gleichheitsnebenbedingungen verzichtet, man modelliert diese dann stattdessen als Ordnungskegel mit leerem Inneren. Statt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)\in -K\,,\,h(x)=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)\in -K\,,\,h(x)=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/883cdf6947008e414ec412f1f103786e1bc9834e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.517ex; height:2.843ex;" alt="{\displaystyle g(x)\in -K\,,\,h(x)=0}" loading="lazy"> zu fordern, definiert man einen Kegel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K'=K\times \{0\}}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K'=K\times \{0\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d82be9f14ff8dc37804b45443d4d9d5297d548aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.271ex; height:3.009ex;" alt="{\displaystyle K'=K\times \{0\}}" loading="lazy">. Dann gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (g(x),h(x))\in -K'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (g(x),h(x))\in -K'}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/30fd3c02d755a80cca0505b3c6fe2ed8adbbbed4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.004ex; height:3.009ex;" alt="{\displaystyle (g(x),h(x))\in -K'}" loading="lazy"> genau dann, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)\in -K\,,\,h(x)=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)\in -K\,,\,h(x)=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/883cdf6947008e414ec412f1f103786e1bc9834e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.517ex; height:2.843ex;" alt="{\displaystyle g(x)\in -K\,,\,h(x)=0}" loading="lazy">. Für alle drei Varianten sind die Lagrange-Funktion und das duale Problem in der untenstehenden Tabelle angegeben. Die duale Funktion ist stets von der Form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q(\lambda ,\mu )=\inf _{x\in X}L(x,\lambda ,\mu )}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(\lambda ,\mu )=\inf _{x\in X}L(x,\lambda ,\mu )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3fb4774c94a02daefa5ed4a94d73ad1651afdd45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:23.138ex; height:4.009ex;" alt="{\displaystyle q(\lambda ,\mu )=\inf _{x\in X}L(x,\lambda ,\mu )}" loading="lazy"> bzw., wenn nur eine duale Variable verwendet wird, von der Form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q(\lambda )=\inf _{x\in X}L(x,\lambda )}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(\lambda )=\inf _{x\in X}L(x,\lambda )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e22ab7a88a44e2fac73bf8d9855271142c2b7b3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:18.267ex; height:4.009ex;" alt="{\displaystyle q(\lambda )=\inf _{x\in X}L(x,\lambda )}" loading="lazy">.

<th>Primales Problem</th>

<th>Lagrange-Funktion</th>

<th>Duales Problem

</th></tr>

<tr>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g(x)\preccurlyeq _{K}0\\&h(x)=0\\&x\in X&\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5b7b95b40d96dc8346b986edc313dbb06420560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.505ex; width:45.583ex; height:12.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g(x)\preccurlyeq _{K}0\\&h(x)=0\\&x\in X&\end{aligned}}}" loading="lazy">

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,\lambda ,\mu )=f(x)+\langle \lambda ;g(x)\rangle _{1}+\langle \mu ;h(x)\rangle _{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/50d87e6f111b00ae385b39831aee4a917c458fbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.028ex; height:2.843ex;" alt="{\displaystyle L(x,\lambda ,\mu )=f(x)+\langle \lambda ;g(x)\rangle _{1}+\langle \mu ;h(x)\rangle _{2}}" loading="lazy">

</td>

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda \succcurlyeq _{K^{D}}0\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c441e00c14d375d9553deac9d17bad66ea5ae31d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.278ex; margin-bottom: -0.226ex; width:43.972ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda \succcurlyeq _{K^{D}}0\end{aligned}}}" loading="lazy">

</td></tr>

<tr>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g(x)\in -K\\&h(x)=0\\&x\in X&\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/84a8057c92a3730c347d87a70e4e7c2d9efdcc19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.505ex; width:46.344ex; height:12.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g(x)\in -K\\&h(x)=0\\&x\in X&\end{aligned}}}" loading="lazy">

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,\lambda ,\mu )=f(x)+\langle \lambda ;g(x)\rangle _{1}+\langle \mu ;h(x)\rangle _{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/50d87e6f111b00ae385b39831aee4a917c458fbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.028ex; height:2.843ex;" alt="{\displaystyle L(x,\lambda ,\mu )=f(x)+\langle \lambda ;g(x)\rangle _{1}+\langle \mu ;h(x)\rangle _{2}}" loading="lazy">

</td>

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda \in K^{D}\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8e65c1f44e258ad372902965e543bdd4eb02aec7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:43.257ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda \in K^{D}\end{aligned}}}" loading="lazy">

</td></tr>

<tr>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g(x)\in -K\\&x\in X&\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/924a8dde1d085937232c370967821c33914fe212.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:46.344ex; height:9.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g(x)\in -K\\&x\in X&\end{aligned}}}" loading="lazy">

</td>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,\lambda )=f(x)+\langle \lambda ;g(x)\rangle _{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0f5e54b7dea856a1111c551d3b4764b13e8b982f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.975ex; height:2.843ex;" alt="{\displaystyle L(x,\lambda )=f(x)+\langle \lambda ;g(x)\rangle _{1}}" loading="lazy">

</td>

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda )&\\{\text{unter den Nebenbedingungen }}&\lambda \in K^{D}\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f1f8edfdff5323378e59acd92109b5cf6745d2e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:43.257ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda )&\\{\text{unter den Nebenbedingungen }}&\lambda \in K^{D}\end{aligned}}}" loading="lazy">

</td></tr></tbody></table>

Dabei ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:V_{0}\mapsto \mathbb {R} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:V_{0}\mapsto \mathbb {R} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b99e65fa8c5f4fc91c75c4d0d922d09543eadad2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.917ex; height:2.509ex;" alt="{\displaystyle f:V_{0}\mapsto \mathbb {R} }" loading="lazy"> die Zielfunktion, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g:V_{0}\mapsto V_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g:V_{0}\mapsto V_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/16683037f5f49ecd94fb2334284817fb7ab42443.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.486ex; height:2.509ex;" alt="{\displaystyle g:V_{0}\mapsto V_{1}}" loading="lazy">, wobei auf <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/adfdbc929f16cb00bb43289c223651b41f7b9f80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{1}}" loading="lazy"> ein Kegel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> ausgezeichnet ist, der im ersten Fall ein echter Kegel ist, im zweiten und dritten Fall ein konvexer Kegel ist. Es ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h:V_{0}\mapsto V_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h:V_{0}\mapsto V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/97baf476bd68f6c71025c21f69573ba094d085de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.709ex; height:2.509ex;" alt="{\displaystyle h:V_{0}\mapsto V_{2}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda \in V_{1},\,\mu \in V_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda \in V_{1},\,\mu \in V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7eaf2cccc52a47277745ae8df4cbc1999c153a3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.678ex; height:2.676ex;" alt="{\displaystyle \lambda \in V_{1},\,\mu \in V_{2}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Formulierung_für_normierte_Räume">Formulierung für normierte Räume</h3></div>

Für Probleme mit Abbildungen zwischen reellen <a href="Normierter_Raum" title="Normierter Raum">normierten Vektorräumen</a> ist zu beachten, dass kein Skalarprodukt definiert ist. Man wählt stattdessen die <a href="Duale_Paarung" title="Duale Paarung">duale Paarung</a>. Dementsprechend sind die dualen Variablen aus dem <a href="Dualraum" title="Dualraum">Dualraum</a> des Vektorraumes.

Ist ein Problem der Form

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g(x)\in -K\\&h(x)=0\\&x\in X&\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/84a8057c92a3730c347d87a70e4e7c2d9efdcc19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.505ex; width:46.344ex; height:12.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g(x)\in -K\\&h(x)=0\\&x\in X&\end{aligned}}}" loading="lazy"></dd></dl>

gegeben, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:V_{0}\mapsto \mathbb {R} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:V_{0}\mapsto \mathbb {R} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b99e65fa8c5f4fc91c75c4d0d922d09543eadad2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.917ex; height:2.509ex;" alt="{\displaystyle f:V_{0}\mapsto \mathbb {R} }" loading="lazy"> die Zielfunktion, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}:V_{0}\mapsto V_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}:V_{0}\mapsto V_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3eebefc4f2b247bad7a30f1deefa4fdc0629481e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.279ex; height:2.509ex;" alt="{\displaystyle g_{i}:V_{0}\mapsto V_{1}}" loading="lazy"> die Ungleichungsrestriktionsfunktionen und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{j}:V_{0}\mapsto V_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{j}:V_{0}\mapsto V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/acfc9b9b6c41f6945781ba33096a6c8805875451.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.619ex; height:2.843ex;" alt="{\displaystyle h_{j}:V_{0}\mapsto V_{2}}" loading="lazy"> die Gleichungsrestriktionsfunktion sind. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> sei ein Ordnungskegel auf <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/adfdbc929f16cb00bb43289c223651b41f7b9f80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{1}}" loading="lazy"> und es seien <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{0},V_{1},V_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{0},V_{1},V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2af04e85e7f830bee62286ad36473508a2833236.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.296ex; height:2.509ex;" alt="{\displaystyle V_{0},V_{1},V_{2}}" loading="lazy"> Banachräume. Die Lagrange-Funktion lautet dann

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(x,u,v)=f(x)+u(g(x))+v(h(x)).}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0b3509112bc491628f2e353b0a1bd3646787c7aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:37.899ex; height:2.843ex;" alt="{\displaystyle L(x,u,v)=f(x)+u(g(x))+v(h(x)).}" loading="lazy"></dd></dl>

Dabei ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> aus dem Dualraum <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}^{*}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1}^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6d65e358b2cd3daeaeeea0566ca1aa37bad67f10.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.971ex; height:2.843ex;" alt="{\displaystyle V_{1}^{*}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> aus dem Dualraum <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{2}^{*}.}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{2}^{*}.}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b08166bcfc6807a99dcefa962ae78daa388a70da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.618ex; height:2.843ex;" alt="{\displaystyle V_{2}^{*}.}" loading="lazy">

Die duale Funktion ist dann wieder

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(u,v)=\inf _{x\in X}L(x,u,v)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a59ce4ca45d9d782d1c6beef9ed9e1db1a845564.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:22.539ex; height:4.009ex;" alt="{\displaystyle q(u,v)=\inf _{x\in X}L(x,u,v)}" loading="lazy"></dd></dl>

und damit lautet das duale Problem:

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(u,v)&\\{\text{unter den Nebenbedingungen }}&u\in K^{*}\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/193689b7db6e16cccb2b055c647a3c3ab7eda7cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:42.693ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&q(u,v)&\\{\text{unter den Nebenbedingungen }}&u\in K^{*}\end{aligned}}}" loading="lazy"></dd></dl>

Dabei ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ee44d723b0d9bf440e04a664ea1e6e1958d743de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.148ex; height:2.343ex;" alt="{\displaystyle K^{*}}" loading="lazy"> der <a href="Dualer_Kegel" title="Dualer Kegel">duale Kegel</a>, der in diesem Fall aber eine <a href="Teilmenge" title="Teilmenge">Teilmenge</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}^{*}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1}^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6d65e358b2cd3daeaeeea0566ca1aa37bad67f10.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.971ex; height:2.843ex;" alt="{\displaystyle V_{1}^{*}}" loading="lazy"> ist.

Formulierungen für alternative Problemstellungen laufen analog zu den Problemen für Abbildungen zwischen Hilberträumen. Die duale Paarung ersetzt jeweils das Skalarprodukt, die dualen Variablen befinden sich im Dualraum.

<div class="mw-heading mw-heading3"><h3 id="Schwache_und_starke_Dualität">Schwache und starke Dualität</h3></div>

Die schwache Dualität gilt auch für die beiden allgemeineren Formulierungen. Für den Beweis in der Hilbertraumformulierung nutzt man aus, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle a;b\rangle \leq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle a;b\rangle \leq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fc00090a6e91b3f447a09b2bc648b14bcc390128.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.332ex; height:2.843ex;" alt="{\displaystyle \langle a;b\rangle \leq 0}" loading="lazy"> ist, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\succcurlyeq _{K^{D}}0}">

<msub>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\succcurlyeq _{K^{D}}0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2840caa142674676ae821d33ae8bcffa7664c616.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.473ex; height:2.843ex;" alt="{\displaystyle a\succcurlyeq _{K^{D}}0}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\preccurlyeq _{K}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\preccurlyeq _{K}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/22d22db5659e501790951a218400ec0b0a3934eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.144ex; height:2.509ex;" alt="{\displaystyle b\preccurlyeq _{K}}" loading="lazy"> gilt (für Ordnungskegel erhält man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in K^{D},\,b\in -K\implies \langle a;b\rangle \leq 0}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in K^{D},\,b\in -K\implies \langle a;b\rangle \leq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5d60cb56db521ae30cea8bb352b4145a096a8327.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.608ex; height:3.176ex;" alt="{\displaystyle a\in K^{D},\,b\in -K\implies \langle a;b\rangle \leq 0}" loading="lazy">). In normierten Räumen gelten analoge Aussagen mit dem Unterschied, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> ein Element des Dualraumes ist: Gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in K^{*},b\in -K}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in K^{*},b\in -K}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a66f8d037edeaf6abfe7c867262a78167a45fbc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.965ex; height:2.676ex;" alt="{\displaystyle a\in K^{*},b\in -K}" loading="lazy">, so folgt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a(b)\leq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a(b)\leq 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f02c8bd4d95797cc115c1abed61849b8ce22eb16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.298ex; height:2.843ex;" alt="{\displaystyle a(b)\leq 0}" loading="lazy">.

Die starke Dualität wird in den allgemeineren Fällen identisch zum gewöhnlichen Fall definiert. Auch im verallgemeinerten Fall existieren Regularitätsvoraussetzungen wie die <a href="Slater-Bedingung" title="Slater-Bedingung">Slater-Bedingung</a>, die starke Dualität garantieren.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2004, ISBN 3-540-43575-1.</li>

<li>Stephan Boyd, Lieven Vandenberghe: Convex Optimization. Cambridge University Press, 2004, ISBN 978-0-521-83378-3 (<a rel="nofollow" class="external text" href="https://web.stanford.edu/~boyd/cvxbook/">online</a>).</li>

<li>C. Geiger, C. Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, 2002, ISBN 3-540-42790-2.</li>

<li>Johannes Jahn: Introduction to the Theory of Nonlinear Optimization. 3. Auflage. Springer, Berlin 2007, ISBN 978-3-540-49378-5.</li></ul>

<div>

Normdaten (Sachbegriff): <a href="Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a>: <a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4788589-0">4788589-0</a> </div>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-05-20" href="https://de.wikipedia.org/wiki/?title=Lagrange-Dualit%C3%A4t&oldid=256162175">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>